1. Technical Field
The present invention relates to task management in a data processing system, and specifically to allocation of a shared resource among multiple competing requests.
2. Background Art
In general, in the descriptions that follow, I will italicize the first occurrence of each special term of art which should be familiar to those skilled in the art of communication system security. In addition, when I first introduce a term that I believe to be new or that I will use in a context that I believe to be new, I will bold the term and then provide the definition that I intend to apply to that term. In addition, throughout this description, I will use the terms assert and negate when referring to the rendering of a signal, signal flag, status, bit or similar apparatus into its logically true or logically false state, respectively.
Within a data processing system, the various hardware resources are usually controlled by low-level software modules, sometimes called drivers. Basic system functions, on the other hand, such as file or memory management, are performed by mid-level software modules that, in turn, may rely upon one or more of the drivers for actual hardware support. System level functions, such as application and transaction management, are coordinated by upper-level software modules that may themselves rely upon one or more of the lower level modules for support. This hierarchy of system software modules is usually referred to as a operating system or OS. In general, an application program, such as a word processor or a browser, is comprised of one or more high-level modules which may, in the course of their execution, invoke either other application modules or OS modules, as needed, to perform specific functions.
The general process of module invocation and termination, usually referred to as task management, is coordinated by specific operating system modules, collectively referred to as the Task Manager or TM. From the perspective of the TM, a task can be any software module, system or application, that performs a designated function and has regular structured input and regular structured output. For example, so long as an executing module (a requesting task) can construct the appropriate request to the TM to initiate a particular task (a requested task), the requesting task doesn""t care whether the requested task accomplishes that request entirely in software, entirely in hardware, or in a combination of software and hardware. From the perspective of the requesting task, therefore, all lower level support tasks, whether software, hardware or both, can be considered as resources. Task management is thus just a particular form of resource management.
In multi-tasking data processing systems, multiple processes can be active simultaneously, although in a single processor system, only one of the active processes will be in control of the processor at any point in time. By way of example, assume that, at a particular point in time, a Process_A is in control of the processor, and, in particular, that a Task_X of Process_A has just issued a request to the TM that Task_R be performed. Assume also that, since Task_R will take a relatively significant time to complete and that Task_X cannot proceed until Task_R is completed, the TM will take control of the processor away from Task_X of Process_A and give it to, perhaps, a Task_S of a Process_B. Finally, assume that, before Task_R completes the request from Task_X of Process_A, Task_S also requests that Task_R be performed. If, due to the nature of Task_R only one instant can be active at a particular point in time, then a resource conflict has occurred. A typical example is where Task_R xe2x80x9cownsxe2x80x9d exclusive rights to exploit a unique hardware or software component of the system. Access to Task_R must therefore be shared. This shared resource allocation problem can be further complicated if, for any of a number of valid reasons, each process (or each task within each process) is assigned a relative priority: what is to happen, for example, if Process_B has been assigned a higher priority than Process_A?
FIG. 1 illustrates a conventional data processing system 2 having a central processing unit or CPU 4 coupled to multiple special function units or SFUs, via a communication bus 6. Any of a variety of functions may be implemented by SFU18 and SFU210, including arithmetic functions, logical functions, multimedia functions, etc. Each of SFU18 and SFU210 may perform a single function, or may perform multiple functions. Additionally, the data processing system 2 includes a resource 12, which may be another processor, a memory, or any other device accessed by data processing system 2. Within a memory 14 is located an OS 16, and at least one application program 18. Each application program 18 includes a scheduling block, and multiple tasks, such as Task_1 and Task_2. Depending upon various system resource constraints and workload demands, additional application programs (not shown) may be simultaneously active in the memory 14.
Various operating scenarios of the data processing system 2, according to the prior art, are illustrated in FIGS. 2-4. In Case I, illustrated in FIG. 2, OS 16 initiates a Process_A (xe2x80x9cStart_Axe2x80x9d), which may be either an application or system module. During execution, Process_A makes a request to the OS (xe2x80x9cA_Request_Rxe2x80x9d) for use of a shared resource, R, such as a particular shared task resident in the memory 14 or perhaps the resource 12. At this time, OS 16 initiates operation of the shared resource R (xe2x80x9cA_Start_Rxe2x80x9d), which proceeds to perform its designated function. Upon initiating R, OS 16 stores information to identify Process_A as the current process utilizing resource R. While R is running, Process_A may perform other operations until some result or response from R is required (xe2x80x9cA_Read_Rxe2x80x9d). If R is not yet completed, Process_A must wait (indicated in FIG. 2 by the dashed vertical time line). Upon completion, R sends a response to the waiting Process_A (xe2x80x9cR_Response_Axe2x80x9d), and Process_A is then able to continue. Simultaneously, R notifies OS 16 (xe2x80x9cR_Stop_Axe2x80x9d) that it has completed Process_A""s request. When Process_A finally completes its operation, it notifies the OS 16 (xe2x80x9cA_Stopxe2x80x9d).
FIG. 3 illustrates another prior art scenario, Case II, that is similar to Case I, except that a Process_B is initiated (xe2x80x9cStart_Bxe2x80x9d) after Process_A has been initiated (xe2x80x9cStart_Axe2x80x9d). During execution, Process_B also makes a request to OS 16 (xe2x80x9cB_Request_Rxe2x80x9d) for the use of resource R. At the time of this request, R is still performing the request from Process_A. If OS 16 has no mechanism for resolving the conflict or if both Process_A and Process_B have the same or lower priority, Process_B must wait until R completes Process_A""s request. Once R notifies OS 16 (xe2x80x9cR_Stop_Axe2x80x9d) that it has completed the request of Process_A, OS 16 promptly initiates R for Process_B (xe2x80x9cB_Start_Rxe2x80x9d). When resource R completes Process_B""s request, it sends a response to the waiting Process_B (xe2x80x9cR_Response_Bxe2x80x9d), which may now continue. Simultaneously, R notifies OS 16 (xe2x80x9cR_Stop_Bxe2x80x9d) that it has completed Process_B""s request. For simplicity, the ultimate completions of Process_A and Process_B have not been shown.
FIG. 4 illustrates still another prior art scenario, Case III, in which Process_B has been assigned a higher priority than Process_A. In this case, when Process_B requests R (xe2x80x9cB_Request_Rxe2x80x9d), OS 16 immediately initiates R for Process_B (xe2x80x9cB_Start_Rxe2x80x9d), thereby interrupting the operation of R for Process_A. When R completes, it sends a response to Process_B (xe2x80x9cR_Response_Bxe2x80x9d), and, simultaneously, notifies OS 16 (xe2x80x9cR_Stop_Bxe2x80x9d) that Process_B""s request is complete. At that time, OS 16 reinitiates R for Process_A (the second xe2x80x9cA_Start_Rxe2x80x9d).
As can be readily seen, the Case III allocation policy may result in significant loss in system performance, due to the wasted time spent by R servicing the interrupted request of Process_A. In pathological cases, the Process_A request may never be completed due to continual interruptions by requests for R from higher priority processes. One prior art solution is to provide a mechanism for R (or perhaps the requesting Process_A or the OS itself) to periodically store into the memory 14 a status xe2x80x9csnapshotxe2x80x9d or watchpoint consisting of sufficient information to allow later resumption should an interrupt occur. Then, should R be interrupted to service a higher priority process, R can resume operation at the precise point at which the last watchpoint was taken. Thus, except in extreme circumstances, the interrupted process will eventually complete.
In some systems, particular processes may have predetermined time windows within which they must complete. If the TM allows no resource interruption and reallocation, such critical processes may miss their deadlines. For example, Process_B might be a repeating process that monitors an input within a predetermined period, such as looking for an incoming system status signal. Here Process_B has a brief window within which to catch the signal. If Process_A has initiated R, Process_B may not be able to satisfy its deadline if it is forced to wait until R has completed Process_A""s request. Although the prior art watchpoint mechanism would allow Process_B to interrupt Process_A""s use of R, it assumes that, prior to interruption, the watchpoint was indeed taken. Depending upon the size of the watchpoint and the frequency with which they are taken, significant system resources and performance may thus be unavailable for application to more useful activities.
One additional problem with prior art resource allocation mechanisms is that certain operations are inherently atomic and are simply not amenable to interruption/resumption. The higher priority requester may miss a deadline if it must wait until a particularly long-running operation reaches a point at which it can be safely interrupted. For example, in some serial communication systems, end-to-end synchronization must be maintained and therefore a transmission cannot be interrupted without loss of the entire transaction. Similarly, in a packetized transaction, used in many communication networks, the packet transmission must be restarted after interrupt rather than resuming from the point of interrupt. The resulting degradation in system performance can be significant.
In all of these cases, the TM is required to dynamically allocate and, perhaps, reallocate shared resources. Should a conflict occur, the TM must first decide whether to allow Process_A""s use of the resource to continue to completion, or to interrupt it so that Process_B can use the resource. If the latter choice is made, then the TM must determine if there is a recent watchpoint which can be used to resume the interrupted process when the higher priority process has completed, or, if not, to simply restart the resource after the interruption. Usually, the choice is made at the time the OS is designed and cannot be changed to meet different system criteria. In order to make such decisions in a more effective manner, either the TM must have access to additional information regarding the nature of the requesting processes or the requesting processes themselves must be allowed to participate in the decision process.
There is need therefore for a method for allocating a shared resource which allows each process some level of participation in the allocation decision by the TM. Additionally, a need exists for a more flexible method of allocating a shared resource to meet the timing of all processes in the system.
My invention comprises a task management method in which each requesting task is responsible for deciding on an appropriate course of action in the event the requested task is interrupted for any reason. Preferably, the requesting task is capable of periodically requesting (and saving) the then-current status of the requested task, and the requesting task is capable of providing, if requested, sufficient status information to allow an interrupted task to be resumed. At a minimum, the requested task must be able to inform the requesting task as to the identity of the requesting task to which the requested task is then currently allocated. Should the requesting task determine from such status information that the requested task has been reallocated by the task manager, the requesting task will invoke an exception handler to deal appropriately with the situation.